package com.LeetCode.StackAndHeap;

import org.junit.Test;

import java.util.*;

/**
 * 最接近原点的 K 个点
 */
public class FindKClosePoint {

    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> cal(b) - cal(a));
        int[][] ans = new int[K][2];

        for(int i = 0; i<K; i++){
            queue.offer(points[i]);
        }

        for(int i = K; i<points.length; i++){
            assert queue.peek() != null;
            if(cal(points[i]) < cal(queue.peek())){
                queue.poll();
                queue.offer(points[i]);
            }
        }



        for(int i = 0; i<K; i++){
            ans[i] = queue.poll();
        }
        return ans;
    }

    private int cal(int[] a){
        return (a[0] * a[0]) + (a[1] * a[1]);
    }

    @Test
    public void test(){
        int[][] points = {{3,3},{5,-1},{-2,4}};
        for(int[] arr : kClosest(points,2)){
            for(int point : arr){
                System.out.println(point);
            }
        }
    }

}
